Defining phylogenetic networks using ancestral profiles.

Rooted phylogenetic networks provide a more complete representation of the ancestral relationship between species than phylogenetic trees when reticulate evolutionary processes are at play. One way to reconstruct a phylogenetic network is to consider its 'ancestral profile' (the number of paths from each ancestral vertex to each leaf). In general, this information does not uniquely determine the underlying phylogenetic network. A recent paper considered a new class of phylogenetic networks called 'orchard networks' where this uniqueness was claimed to hold. Here we show that an additional restriction on the network, that of being 'stack-free', is required in order for the original uniqueness claim to hold. On the other hand, if the additional stack-free restriction is lifted, we establish an alternative result; namely, there is uniqueness within the class of orchard networks up to the resolution of vertices of high in-degree.

Not all phylogenetic networks are leaf-reconstructible.

Unrooted phylogenetic networks are graphs used to represent reticulate evolutionary relationships. Accurately reconstructing such networks is of great relevance for evolutionary biology. It has recently been conjectured that all unrooted phylogenetic networks for at least five taxa can be uniquely reconstructed from their subnetworks obtained by deleting a single taxon. Here, we show that this conjecture is false, by presenting a counter-example for each possible number of taxa that is at least 4. Moreover, we show that the conjecture is still false when restricted to binary networks. This means that, even if we are able to reconstruct the unrooted evolutionary history of each proper subset of some taxon set, this still does not give us enough information to reconstruct their full unrooted evolutionary history.

A class of phylogenetic networks reconstructable from ancestral profiles.

Rooted phylogenetic networks provide an explicit representation of the evolutionary history of a set X of sampled species. In contrast to phylogenetic trees which show only speciation events, networks can also accommodate reticulate processes (for example, hybrid evolution, endosymbiosis, and lateral gene transfer). A major goal in systematic biology is to infer evolutionary relationships, and while phylogenetic trees can be uniquely determined from various simple combinatorial data on X, for networks the reconstruction question is much more subtle. Here we ask when can a network be uniquely reconstructed from its 'ancestral profile' (the number of paths from each ancestral vertex to each element in X). We show that reconstruction holds (even within the class of all networks) for a class of networks we call 'orchard networks', and we provide a polynomial-time algorithm for reconstructing any orchard network from its ancestral profile. Our approach relies on establishing a structural theorem for orchard networks, which also provides for a fast (polynomial-time) algorithm to test if any given network is of orchard type. Since the class of orchard networks includes tree-sibling tree-consistent networks and tree-child networks, our result generalise reconstruction results from 2008 and 2009. Orchard networks allow for an unbounded number k of reticulation vertices, in contrast to tree-sibling tree-consistent networks and tree-child networks for which k is at most 2|X|-4 and |X|-1, respectively.

Efficiently sampling the realizations of bounded, irregular degree sequences of bipartite and directed graphs.

Since 1997 a considerable effort has been spent on the study of the swap (switch) Markov chains on graphic degree sequences. All of these results assume some kind of regularity in the corresponding degree sequences. Recently, Greenhill and Sfragara published a breakthrough paper about irregular normal and directed degree sequences for which rapid mixing of the swap Markov chain is proved. In this paper we present two groups of results. An example from the first group is the following theorem: let [Formula: see text] be a directed degree sequence on n vertices. Denote by Δ the maximum value among all in- and out-degrees and denote by [Formula: see text] the number of edges in the realization. Assume furthermore that [Formula: see text]. Then the swap Markov chain on the realizations of [Formula: see text] is rapidly mixing. This result is a slight improvement on one of the results of Greenhill and Sfragara. An example from the second group is the following: let d be a bipartite degree sequence on the vertex set U ⊎ V, and let 0 < c1 ≤ c2 < |U| and 0 < d1 ≤ d2 < |V| be integers, where c1 ≤ d(v) ≤ c2: ∀v ∈ V and d1 ≤ d(u) ≤ d2: ∀u ∈ U. Furthermore assume that (c2 - c1 - 1)(d2 - d1 - 1) < max{c1(|V| - d2), d1(|U| - c2)}. Then the swap Markov chain on the realizations of d is rapidly mixing. A straightforward application of this latter result shows that when a random bipartite or directed graph is generated under the Erdos-Rényi G(n, p) model with mild assumptions on n and p then the degree sequence of the generated graph has, with high probability, a rapidly mixing swap Markov chain on its realizations.

Exploring the Tiers of Rooted Phylogenetic Network Space Using Tail Moves.

Popular methods for exploring the space of rooted phylogenetic trees use rearrangement moves such as rooted Nearest Neighbour Interchange (rNNI) and rooted Subtree Prune and Regraft (rSPR). Recently, these moves were generalized to rooted phylogenetic networks, which are a more suitable representation of reticulate evolutionary histories, and it was shown that any two rooted phylogenetic networks of the same complexity are connected by a sequence of either rSPR or rNNI moves. Here, we show that this is possible using only tail moves, which are a restricted version of rSPR moves on networks that are more closely related to rSPR moves on trees. The connectedness still holds even when we restrict to distance-1 tail moves (a localized version of tail moves). Moreover, we give bounds on the number of (distance-1) tail moves necessary to turn one network into another, which in turn yield new bounds for rSPR, rNNI and SPR (i.e. the equivalent of rSPR on unrooted networks). The upper bounds are constructive, meaning that we can actually find a sequence with at most this length for any pair of networks. Finally, we show that finding a shortest sequence of tail or rSPR moves is NP-hard.

Approximate Counting of Graphical Realizations.

In 1999 Kannan, Tetali and Vempala proposed a MCMC method to uniformly sample all possible realizations of a given graphical degree sequence and conjectured its rapidly mixing nature. Recently their conjecture was proved affirmative for regular graphs (by Cooper, Dyer and Greenhill, 2007), for regular directed graphs (by Greenhill, 2011) and for half-regular bipartite graphs (by Miklós, Erdos and Soukup, 2013). Several heuristics on counting the number of possible realizations exist (via sampling processes), and while they work well in practice, so far no approximation guarantees exist for such an approach. This paper is the first to develop a method for counting realizations with provable approximation guarantee. In fact, we solve a slightly more general problem; besides the graphical degree sequence a small set of forbidden edges is also given. We show that for the general problem (which contains the Greenhill problem and the Miklós, Erdos and Soukup problem as special cases) the derived MCMC process is rapidly mixing. Further, we show that this new problem is self-reducible therefore it provides a fully polynomial randomized approximation scheme (a.k.a. FPRAS) for counting of all realizations.